1. Field of the Invention
The present invention relates to the field of electronic memories and, more particularly, to dynamic variable page size translation of addresses. More specifically, the invention relates to translation look-aside buffers (TLB""s) used in variable page size translation of memory addresses. Accordingly, the general objects of the invention are to provide novel methods, apparatus, data structures, etc. of such character.
2. Background of the Invention
Most modem data processing equipment relies on virtual memory to help manage the flow of data. Operating systems using such virtual memory map the user""s view of the memory (the virtual address) to the actual physical location of data in the memory (the physical address). These mappings are either stored in the main memory or cached in buffers in the system. These buffers are called translation look-aside buffers and contain the mapping information necessary to translate virtual addresses into physical addresses.
Generally, memories are broken into separate blocks called pages and for a variety of reasons, these pages can vary greatly in size. Therefore, typical processors support multiple page sizes. The page size determines the number of bits in the virtual address that need to be translated because the offset for a given page can be derived from certain bits in the virtual address. For example, in the case of a 4 Kbyte page size, the 12 least significant (in terms of magnitude) bits of the virtual address (VA[12:0]) need not be translated. In the case of a 4 Mbyte page size, the 22 least significant bits (VA[21:0]) are not translated.
Typical translation look-aside buffers store size-field data in a page table entry array and (with the use of some peripheral circuitry) use this information to determine how many of the virtual address bits need to be translated and how many of the virtual address bits can be bypassed. These conventional TLB""s utilize external control logic to decode the size-field data read from the TLB and additional bypass multiplexers to select either the virtual address bits or the physical address bits, depending on the situation for a particular address. Because such circuitry is synchronous, the additional control logic and multiplexers add significant delay in the critical path of the address data. This delay represents an undesirable obstacle to the implementation of higher clock-speed processors. Given the constant drive to create faster and faster processors, limits such as these pose a significant impediment to the achievement of higher clock speeds demanded by the next generation of processors. Conventional TLB""s of this nature are described in more detail immediately below.
FIG. 1 is a diagram of a conventional variable page size TLB 100 shown in combination with the requisite peripheral circuitry. TLB 100 and the peripheral circuitry of FIG. 1, collectively, receive a virtual address VA[63:0] 101 and translate that address into a translated physical address TPA[40:0]. In particular, TLB 100 includes a content addressable memory (CAM) 102 and a page table entry array (RAM) 104. A representative page table entry 106 in RAM 104 stores a validity bit (xe2x80x9cVxe2x80x9d) 108, size-field bits (xe2x80x9cSZ[1:0]xe2x80x9d) 110, physical address bits (xe2x80x9cPA[40:13]xe2x80x9d) 112 and status bits (xe2x80x9cSTATUS[8:0]xe2x80x9d) 114. As with the entirety of TLB 100, the function of the validity bit 108 and status bits 114 are well known in the art. Since these components, however, are less important to the operation of the invention, they need not be discussed in further detail herein. It will also be understood that the virtual addresses discussed herein have omitted various xe2x80x9ccontentxe2x80x9d bits which vary from system to system.
FIG. 1A is a table showing typical encoded size-field data for the four different page sizes supported by TLB 100 of FIG. 1. As shown in FIG. 1A, the size-field data consists of 2 bits, SZ[1:0], each different combination of these two bits representing a different page size. The data structure for the information stored in each page table entry is shown in FIG. 1B (see also page table entry 106 of FIG. 1). Those of ordinary skill will recognize the structure and function of data structure 130.
Referring back to FIG. 1, external size-field control logic 116 is coupled to the TLB 100. Further, external multiplexers 118, 120, and 122 are coupled to TLB 100, virtual address VA[63:0] 101 and size-field control logic 116. Among other things it will be appreciated that TLB 100 includes a plurality of page table entries 106xe2x80x2 which are substantially identical in function and structure to entry 106. The operation of TLB 100 will now be illustrated in conjunction with the encoded size-field data shown in FIG. 1A.
With joint reference to FIGS. 1 and 1A, CAM 102 receives VA[63:0] 101, generates a CAM match signal 124 when the virtual address matches a virtual address tag in CAM 102 and sends match signal 124 to page table entry array 104. In response to CAM match signal 124, a corresponding page table entry of RAM 104 (taken to be entry 106 for purposes of illustration) is selected to output the stored physical address bits 112. Note that virtual address bits VA[12:0] of the translated physical address PA [40:0] are never translated because virtual address bits VA[12:0] (corresponding to the minimum page size 8 Kbytes) can always be used as the translated physical address bits TPA[12:0]. Similarly, physical address bits [40:22] are not fed into multiplexers 118, 120 and 122 but used directly as translated physical address bits TPA[40:22] (always translated), because these bits represent blocks of data larger than the maximum page size of 4 Mbytes.
Continuing the discussion above with respect to address bits which are not directly output, CAM match signal 124 identifies a page table entry which corresponds to the matched virtual address tag of CAM 102 and size-field control logic 116 receives the size-field data SZ[1:0] from that page table entry. The size-field control logic then decodes this data and generates select signals which control multiplexers 118, 120, and 122. If SZ[1:0] is xe2x80x9c11xe2x80x9d (representing a 4 Mbyte page size), then size-field control logic 116 generates select signals to select the virtual address bits VA[21:19], VA[18:16], and VA[15:13] in multiplexers 118, 120, and 122, respectively. This is because none of the physical address bits PA[21:19], PA[18:16] and PA[15:13] are necessary. If SZ[1:0] is xe2x80x9c10xe2x80x9d (representing a 512 Kbyte page size), then size-field control logic 116 generates select signals to select the physical address bits PA[21:19] in multiplexer 118 and virtual address bits VA[18:16] and VA[15:13] in the multiplexers 120 and 122, respectively. This is because the physical address bits PA[18:16] and PA[15:13] are not necessary. If SZ[1:0] is xe2x80x9c01xe2x80x9d (representing a 64 Kbyte page size), then size-field control logic 116 generates select signals to select the physical address bits PA[21:19] and PA[ 18:16] in multiplexers 118 and 120, respectively, and virtual address bits VA[15:13] in multiplexer 122. This is because the physical address bits PA[15:13] are not necessary. Finally, if SZ[1:0] is xe2x80x9c00xe2x80x9d (representing a 8 Kbyte page sizexe2x80x94the minimum page size), then size-field control logic 116 generates select signals to select the physical address bits PA[21:19], PA[18:16] and PA[15:13] in multiplexers 118, 120 and 122, respectively. In this case, all the physical address bits PA[21:19], PA[18:16] and PA[15:13] are necessary.
FIG. 1C is a diagram of a representative RAM cell 180 for storing a single bit of data (typically, but not necessarily, a physical address bit) and a sense amplifier 182 in conventional TLB 100. As shown, RAM cell 180 is a conventional latch that is capable of storing a single bit. When data is output from RAM cell 180, that data is amplified by sense amplifier 182 for compatibility with external multiplexers 118, 120 and 122 of FIG. 1. As is known in the art, all of the various RAM cells of the page table entry array (RAM 104) are identical to that of RAM cell 180. Thus, the values of xe2x80x9cPA[i]xe2x80x9d and xe2x80x9cPA[i] barxe2x80x9d as shown in FIG. 1C should be understood as being replaced by xe2x80x9cVxe2x80x9d and xe2x80x9cV barxe2x80x9d; xe2x80x9cSTATUS [i]xe2x80x9d and xe2x80x9cSTATUS [i] barxe2x80x9d; and xe2x80x9cSZ[i]xe2x80x9d and xe2x80x9cSZ[i] barxe2x80x9d depending on the location and purpose of this RAM cell.
Although conventional TLB 100 is capable of distinguishing different page sizes and outputting appropriate physical addresses by using the size-field control logic and multiplexers as described above, these components add significant and undesirable delay to the critical path of the address data. Also, translation of the virtual addresses commences after CAM 102 performs the CAM match. This also adds a significant and undesirable delay to the critical path of the address data. In total, because this system is synchronous it requires at least two clock cycles (i.e., four phases) to translate virtual address VA[63:0] 101 into a translated physical address TPA[40:0].
The above-described and other limitations and deficiencies of the related art are eliminated with the present invention by providing methods, apparatus, data structures, etc., which are capable of faster dynamic variable page size translation of addresses. In particular, the present invention enables faster translation by eliminating unnecessary circuitry otherwise present in the critical path of the address data. Furthermore, the invention enables faster bypass of such translation by eliminating unnecessary circuitry otherwise present in the critical path of the address data. With the advent of the present invention, translation of virtual address data can occur in as little as one clock cycle.
In one form, the present invention comprises a translation look-aside buffer for translating virtual addresses into physical addresses in a variable page size memory having N page sizes, where N is an integer greater than 1. This translation look-aside buffer receives virtual addresses and includes a CAM and a page table entry array. The CAM stores virtual address tags corresponding to the physical addresses. The page table entry array is coupled to the CAM, includes a plurality of page table entries, and stores physical address corresponding to the virtual address tags of the CAM. Each of the page table entries has at least a plurality of first-type memory cells grouped in Nxe2x88x921 cell groups and at least a plurality of Nxe2x88x921 second-type memory cells. Each of the second-type memory cells is coupled to a cell group and stores size-field data relating to the associated cell group. Responsive to appropriate signals, and depending on the size-field data, the TLB selects between the received virtual address bits and the stored physical address bits and outputs a translated physical address. In particular, the physical address bits stored in the first-type memory cells are output when the size-field data is in a first state. Conversely, the virtual address bits corresponding to the coupled cell group are output when the size-field data is in a second state.
In another form, each first-type memory cell has a physical address latch for storing a single physical address bit, dynamic read circuitry and a multiplexer coupled to the latch and read circuitry. The multiplexer receives a single virtual address bit and a single physical address bit stored in the latch. Responsive to a select-signal, the multiplexer outputs the physical address bit via the read circuitry when the size-field data is in the first state, but outputs the virtual address bit via the read circuitry when the size-field data is in the second state.
The present invention also includes novel RAM cells for a translation look-aside buffer of the type described above. These RAM cells each include a physical address latch for storing a physical address bit and a multiplexer coupled to the latch. The multiplexer receives a physical address bit from the latch and a virtual address bit. The multiplexer outputs the physical address bit when the size-field data is in a first state, but outputs the virtual address bit when the size-field data is in a second state.
Another form of the present invention includes methods of translating virtual addresses into physical addresses using a translation look-aside buffer of the type discussed above. These methods include reading a size-field associated with a group of physical address bits and selecting, as part of a translated physical address output from the TLB, physical address bits when the size-field is in a first state and selecting, as part of the output of the TLB, virtual address bits when the size-field is in a second state.
The present invention also enables methods of managing data in a translation look-aside buffer of the type discussed immediately above. Such methods entail (1) storing physical address data which is grouped into Nxe2x88x921 groups, where each bit-group comprises a plurality of physical address bits; and (2) storing Nxe2x88x921 size-field bits associated with respective bit-groups. In such methods, the physical address bits of the associated bit-group are output as part of a translated physical address when the associated size-field bits are stored in a first state, and the virtual address bits corresponding to the bit-group are output as part of the translated physical address when the associated size-field bits are stored in a second state.
One additional feature enabled by the present invention is a translation bypass function which bypasses the translation process and, therefore, passes the received virtual address as the address exiting the TLB. The translation bypass circuitry can accomplish this function in as little as one clock cycle and without the need for any peripheral circuitry.
Numerous other benefits and advantages of the present invention will become apparent to those of ordinary skill in the art from the detailed description of the invention, from the claims and from the accompanying drawings.